#include <iostream>
#include <vector>
#include "lib/list.h"
using namespace std;

ListNode* findNodeInLoop(ListNode* phead) {
  auto slow_node = phead->next;
  if (slow_node == nullptr) {
    return nullptr;
  }
  auto fast_node = slow_node->next;
  while (fast_node != nullptr && slow_node != nullptr) {
    if (fast_node == slow_node) {
      return fast_node;
    }
    slow_node = slow_node->next;
    fast_node = fast_node->next;
    if (fast_node != nullptr)
      fast_node = fast_node->next;
  }
  return nullptr;
}

int getNumOfLoop(ListNode* pNode) {
  int ret = 1;
  auto node = pNode;
  while (node->next != pNode) {
    node = node->next;
    ++ret;
  }
  return ret;
}

ListNode* findEntryNode(ListNode* phead) {
  if (phead == nullptr) {
    return nullptr;
  }
  auto node = findNodeInLoop(phead);
  if (node == nullptr) {
    return nullptr;
  }
  int num_of_loop = getNumOfLoop(node);
  auto fast_node = phead;
  auto slow_node = phead;
  for (int i = 0; i < num_of_loop; ++i) {
    fast_node = fast_node->next;
  }
  while (fast_node != slow_node) {
    fast_node = fast_node->next;
    slow_node = slow_node->next;
  }
  return fast_node;
}

int main() {
  auto node1 = CreateNode(1);
  auto node2 = CreateNode(2);
  auto node3 = CreateNode(3);
  auto node4 = CreateNode(4);
  auto node5 = CreateNode(5);
  auto node6 = CreateNode(6);

  ConnectNode(node1, node2);
  ConnectNode(node2, node3);
  ConnectNode(node3, node4);
  ConnectNode(node4, node5);
  ConnectNode(node5, node6);
  ConnectNode(node6, node3);

  ListNode* node = findEntryNode(node1);
  cout << "The entry of loop list is: " << node->value << endl;
  
  return 0;
}
